//
// Created by TianBo on 2022/5/30.
//

// size相等放大顶堆，大顶堆top放小顶堆
// size不等放小顶堆，小顶堆top放大顶堆

#include "iostream"
#include "vector"
#include "queue"

using namespace std;

class MedianFinder {
public:
    /** initialize your data structure here. */
    MedianFinder() {

    }

    void addNum(int num) {
        if(bigHeap.size() == smallHeap.size())
        {
            bigHeap.push(num);
            smallHeap.push(bigHeap.top());
            bigHeap.pop();
        }
        else
        {
            smallHeap.push(num);
            bigHeap.push(smallHeap.top());
            smallHeap.pop();
        }
    }

    double findMedian() {
        return bigHeap.size() == smallHeap.size() ? (smallHeap.top() + bigHeap.top())/2 : smallHeap.top();
    }
private:
    priority_queue<double> bigHeap;
    priority_queue<double,vector<double>,greater<double>> smallHeap;
};

int main()
{
    MedianFinder* obj = new MedianFinder();
    obj->addNum(1);
    obj->addNum(2);
    cout<<obj->findMedian()<<endl;
    obj->addNum(3);
    cout<<obj->findMedian()<<endl;
    return 0;
}